#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int GCD(int a, int b) {
    return a%b==0? b : GCD(b, a%b);
}
int Euler(int a) {
    int res=0;
    for (int i=1; i<=a; ++i) {
        if (GCD(i, a)==1) ++res;
    }
    return res;
}
int main() {
    int ask;
    while (cin>>ask) {
        if (ask%2==0 || ask==1) {
            printf("2^? mod %d = 1\n", ask);
        }
        else {
            printf("2^%d mod %d = 1\n", Euler(ask), ask);
        }
    }
    return 0;
}
